package com.数组中的逆序对;

public class Solution {

	public int InversePairs(int [] array) {
        if(array==null||array.length==0){
            return 0;
        }
        int copy[] = new int [array.length];
        for(int i=0;i<array.length;i++){
            copy[i] = array[i];
        }
        int count=InversePairsCore(array,copy,0,array.length-1);
        return count;
    }
	private int InversePairsCore(int [] array,int [] copy,int low,int high) {
		if(low==high) {
			return 0;
		}
		int mid=(low+high)/2;
		int left=InversePairsCore(array,copy,low,mid);
		int right =InversePairsCore(array,copy,mid+1,high);
		int i=mid;
		int j=high;
		int count=0;
		int locCopy = high;
		while(i>=low&&j>mid) {
			if(array[i]>array[j]) {
				count=count+j-mid;
				copy[locCopy--]=array[i--];
			}
			else {
				copy[locCopy--]=array[j--];
			}
		}
		while(i>=low) {
			copy[locCopy--]=array[i--];
		}
		while(j>mid) {
			copy[locCopy--]=array[j--];
		}
		for(int s=low;s<=high;s++) {
			array[s]=copy[s];
		}
		return left+right+count;
	}

}
